#include "stdafx.h"
#include "cassert"
#include "mylib.h"

int partsort(int* pIn,int p,int q)
{
	int i=p+1;
	int key=pIn[p];
	for (int j=p+1;j<=q;++j)
	{
		if (pIn[j]<key)
		{
			exchange(&pIn[j],&pIn[i]);
			++i;
		}
	}
	exchange(&pIn[p],&pIn[i-1]);
	return i-1;
}

void quicksort(int* pIn,int p,int q)
{
	assert(p<=q);
	if (p==q)
	{
		return;
	}
	int mid=partsort(pIn,p,q);
	if (p<mid)
	{
		quicksort(pIn,p,mid-1);
	}
	if (q>mid)
	{
		quicksort(pIn,mid+1,q);
	}	
}